A predictive controller, such as model predictive control (MPC), is used in many applications to control complex dynamical systems. Examples of such systems include production lines, vehicles, satellites, engines, robots, power generators and other numerically controlled machines.
Dynamic optimization based predictive control and estimation can significantly speed up the design process for the controller and estimator. In addition, dynamic optimization allows to directly take control or estimation objectives into account as well as the system dynamics and constraints or limitations related to the states and controls of the system. For real-time applications of predictive control or estimation, an optimal control problem needs to be solved under strict timing constraints, often on embedded hardware with limited computational resources.
Most embedded optimization methods that have successfully been applied to real-time optimal control rely on direct linear algebra routines, see, e.g., U.S. 2004/0107012. However, the computational complexity of those direct solution procedures is O(Nm3), when explicitly taking the block-structured sparsity of the optimization problem into account in a second order optimization method. This means that the computational cost scales linearly with the horizon length, N, but cubically with the number of states and controls of the system, i.e., m. The latter cubic complexity is undesirable for some real-time applications of optimal control and estimation. On the other hand, after eliminating the state variables from the optimization problem based on the discrete-time dynamics of the system, the use of a first order optimization method alternatively results in a computational complexity of O(N2m2). The computational cost scales quadratically with the number of states and controls of the system, i.e., in, but it scales also quadratically with the horizon length, N. The latter quadratic complexity is undesirable for some real-time applications of optimal control and estimation.